﻿#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//
//你不需要 保留 每个分区中各节点的初始相对位置。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/partition-list-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
  struct ListNode {
      int val;
      struct ListNode *next;
 };
  struct ListNode* partition(struct ListNode* head, int x) {
      struct ListNode* cur = head;
      struct ListNode* smalltail = NULL;
      struct ListNode* smallhead = NULL;
      struct ListNode* greaterhead = NULL;
      struct ListNode* greatertail = NULL;
      while (cur)
      {
          if (cur->val < x)
          {
              if (smalltail == NULL)
              {
                  smalltail = smallhead = cur;
              }
              else
              {
                  smalltail->next = cur;
                  smalltail = cur;
              }
              cur = cur->next;
              smalltail->next = NULL;

          }
          else
          {
              if (greatertail == NULL)
              {
                  greatertail = greaterhead = cur;
              }
              else
              {
                  greatertail->next = cur;
                  greatertail = cur;

              }
              cur = cur->next;
              greatertail->next = NULL;
          }

      }
      if (smalltail)
      {
          smalltail->next = greaterhead;
          return smallhead;
      }
      return head;


  }
 
 